#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <fcntl.h>
#include <unistd.h> // 包含close函数

#include <errno.h>

// 定义结构体用于存储用户输入的SQL语句或元命令
typedef struct {
    char *buffer;
    size_t buffer_length;
    ssize_t input_length;
} InputBuffer;

// 定义枚举类型用于表示元命令的执行结果
typedef enum {
    META_COMMAND_SUCCESS,
    META_COMMAND_UNRECOGNIZED_COMMAND,
} MetaCommandResult;

// 定义枚举类型用于表示SQL语句的类型
typedef enum {
    STATEMENT_INSERT,
    STATEMENT_SELECT,
} StatementType;

#define COLUMN_NAME_SIZE 32
#define COLUMN_EMAIL_SIZE 255
// 定义行结构体 Row
typedef struct {
    uint32_t id;                       // 假设有一个id字段
    char name[COLUMN_NAME_SIZE + 1];   // 假设有一个name字段 +1用于存储'\0'
    char email[COLUMN_EMAIL_SIZE + 1]; // 假设有一个email字段 +1用于存储'\0'
} Row;

// 定义结构体用于表示SQL语句
// 该结构体可以扩展以包含更多字段，例如SQL语句的具体内容
typedef struct {
    StatementType type;
    // 其他可能的字段可以在这里添加，例如SQL语句等
    Row row_to_insert; // 用于插入语句的行数据
} Statement;

// 定义枚举类型用于表示SQL语句准备的结果
typedef enum {
    PREPARE_SUCCESS,
    PREPARE_UNRECOGNIZED_STATEMENT,
    PREPARE_SYNTAX_ERROR,
    PREPARE_STRING_TOO_LONG,
    PREPARE_NAGATIVE_ID,
} PrepareResult;

// 定义枚举类型用于表示SQL语句执行的结果
typedef enum {
    EXECUTE_SUCCESS,
    EXECUTE_TABLE_FULL,
    EXECUTE_FAILURE,
    EXECUTE_DUPLICATE_KEY,
} ExecuteResult;

// 实现一个表的结构指向存储行的页并跟踪页中有多少行
const uint32_t PAGE_SIZE = 4096; // 假设每页大小为4096字节
// 定义表的最大页数和行数
#define TABLE_MAX_PAGES 100
#define INVALID_PAGE_NUM UINT32_MAX

/*
存储行数据到叫做页（pages）的内存块中
每页尽量多的去存储适合他的大小的数据（在页的大小范围内，尽量多的存储数据）
在每页中行数据将被序列化为紧凑表示（compact representation）
页只有在需要时候才会被分配
保持固定大小的指针数组指向页
*/
#define size_of_attribute(Struct, Attribute) sizeof(((Struct *)0)->Attribute)

const uint32_t ID_SIZE = size_of_attribute(Row, id);
const uint32_t USERNAME_SIZE = size_of_attribute(Row, name);
const uint32_t EMAIL_SIZE = size_of_attribute(Row, email);
const uint32_t ID_OFFSET = 0;
const uint32_t USERNAME_OFFSET = ID_OFFSET + ID_SIZE;
const uint32_t EMAIL_OFFSET = USERNAME_OFFSET + USERNAME_SIZE;
const uint32_t ROW_SIZE = ID_SIZE + USERNAME_SIZE + EMAIL_SIZE;

/*
增加关于B+树相关的内容
*/
typedef enum {
    NODE_INTERNAL, // 内部节点
    NODE_LEAF,     // 叶子节点
} NodeType;        // 树的节点类型

/*
 * 内部节点和叶子节点的通用头格式布局
 * Common Node Header Layout
 */
const uint32_t NODE_TYPE_SIZE = sizeof(uint8_t);
const uint32_t NODE_TYPE_OFFSET = 0;
const uint32_t IS_ROOT_SIZE = sizeof(uint8_t);
const uint32_t IS_ROOT_OFFSET = NODE_TYPE_SIZE;
const uint32_t PARENT_POINTER_SIZE = sizeof(uint32_t);
const uint32_t PARENT_POINTER_OFFSET = IS_ROOT_OFFSET + IS_ROOT_SIZE;
const uint8_t COMMON_NODE_HEADER_SIZE = NODE_TYPE_SIZE + IS_ROOT_SIZE + PARENT_POINTER_SIZE;

/*
 * 叶子节点头格式布局
 */
const uint32_t LEAF_NODE_NUM_CELLS_SIZE = sizeof(uint32_t); // 该节点的cell个数
const uint32_t LEAF_NODE_NUM_CELLS_OFFSET = COMMON_NODE_HEADER_SIZE;
const uint32_t LEAF_NODE_NEXT_LEAF_SIZE = sizeof(uint32_t);
const uint32_t LEAF_NODE_NEXT_LEAF_OFFSET = LEAF_NODE_NUM_CELLS_OFFSET + LEAF_NODE_NUM_CELLS_SIZE;
const uint32_t LEAF_NODE_HEADER_SIZE = COMMON_NODE_HEADER_SIZE + LEAF_NODE_NUM_CELLS_SIZE + LEAF_NODE_NEXT_LEAF_SIZE;
/*
 * 叶子节点内容格式布局
 */
const uint32_t LEAF_NODE_KEY_SIZE = sizeof(uint32_t);
const uint32_t LEAF_NODE_KEY_OFFSET = 0;
const uint32_t LEAF_NODE_VALUE_SIZE = ROW_SIZE;
const uint32_t LEAF_NODE_VALUE_OFFSET = LEAF_NODE_KEY_OFFSET + LEAF_NODE_KEY_SIZE;
const uint32_t LEAF_NODE_CELL_SIZE = LEAF_NODE_KEY_SIZE + LEAF_NODE_VALUE_SIZE;
const uint32_t LEAF_NODE_SPACE_FOR_CELLS = PAGE_SIZE - LEAF_NODE_HEADER_SIZE;
const uint32_t LEAF_NODE_MAX_CELLS = LEAF_NODE_SPACE_FOR_CELLS / LEAF_NODE_CELL_SIZE;

/*
 * 内部节点头格式布局
 */
const uint32_t INTERNAL_NODE_NUM_KEYS_SIZE = sizeof(uint32_t);
const uint32_t INTERNAL_NODE_NUM_KEYS_OFFSET = COMMON_NODE_HEADER_SIZE;
const uint32_t INTERNAL_NODE_RIGHT_CHILD_SIZE = sizeof(uint32_t);
const uint32_t INTERNAL_NODE_RIGHT_CHILD_OFFSET = INTERNAL_NODE_NUM_KEYS_OFFSET + INTERNAL_NODE_NUM_KEYS_SIZE;
const uint32_t INTERNAL_NODE_HEADER_SIZE =
    COMMON_NODE_HEADER_SIZE + INTERNAL_NODE_NUM_KEYS_SIZE + INTERNAL_NODE_RIGHT_CHILD_SIZE;

/*
 * 内部节点内容格式布局
 */
const uint32_t INTERNAL_NODE_KEY_SIZE = sizeof(uint32_t);
const uint32_t INTERNAL_NODE_CHILD_SIZE = sizeof(uint32_t);
const uint32_t INTERNAL_NODE_CELL_SIZE = INTERNAL_NODE_CHILD_SIZE + INTERNAL_NODE_KEY_SIZE;

/* Keep this small for testing */
const uint32_t INTERNAL_NODE_MAX_KEYS = 3;

// 读取和写入内部节点的方法
uint32_t *internal_node_num_keys(void *node) { return node + INTERNAL_NODE_NUM_KEYS_OFFSET; }

uint32_t *internal_node_right_child(void *node) { return node + INTERNAL_NODE_RIGHT_CHILD_OFFSET; }

uint32_t *internal_node_cell(void *node, uint32_t cell_num) {
    return node + INTERNAL_NODE_HEADER_SIZE + cell_num * INTERNAL_NODE_CELL_SIZE;
}

uint32_t *internal_node_child(void *node, uint32_t child_num) {
    uint32_t num_keys = *internal_node_num_keys(node);
    if (child_num > num_keys) {
        printf("Tried to access child_num %d > num_keys %d\n", child_num, num_keys);
        exit(EXIT_FAILURE);
    } else if (child_num == num_keys) {
        uint32_t *right_child = internal_node_right_child(node);
        if (*right_child == INVALID_PAGE_NUM) {
            printf("Tried to access right child of node, but was invalid page\n");
            exit(EXIT_FAILURE);
        }
        return right_child;
    } else {
        uint32_t *child = internal_node_cell(node, child_num);
        if (*child == INVALID_PAGE_NUM) {
            printf("Tried to access child %d of node, but was invalid page\n", child_num);
            exit(EXIT_FAILURE);
        }
        return child;
    }
}

uint32_t *internal_node_key(void *node, uint32_t key_num) {
    return (void *)internal_node_cell(node, key_num) + INTERNAL_NODE_CHILD_SIZE;
}

// 获取节点类型
NodeType get_node_type(void *node) {
    uint8_t value = *((uint8_t *)(node + NODE_TYPE_OFFSET));
    return (NodeType)value;
}

bool is_node_root(void *node) {
    uint8_t value = *((uint8_t *)(node + IS_ROOT_OFFSET));
    return (bool)value;
}

void set_node_root(void *node, bool is_root) {
    uint8_t value = is_root;
    *((uint8_t *)(node + IS_ROOT_OFFSET)) = value;
}

// 设置节点类型
void set_node_type(void *node, NodeType type) {
    uint8_t value = type;
    *((uint8_t *)(node + NODE_TYPE_OFFSET)) = value;
}

void initialize_internal_node(void *node) {
    set_node_type(node, NODE_INTERNAL);
    set_node_root(node, false);
    *internal_node_num_keys(node) = 0;

    /*
        Necessary because the root page number is 0; by not initializing an internal
        node's right child to an invalid page number when initializing the node, we may
        end up with 0 as the node's right child, which makes the node a parent of the root
    */
    *internal_node_right_child(node) = INVALID_PAGE_NUM;
}

/*
访问叶子节点数据常用的方法
*/

uint32_t *leaf_node_next_leaf(void *node) { return node + LEAF_NODE_NEXT_LEAF_OFFSET; }

// 获取叶子节点的num_cells的地址
uint32_t *leaf_node_num_cells(void *node) { return node + LEAF_NODE_NUM_CELLS_OFFSET; }

// 在叶子节点中，根据node节点(page)的地址和cell的num来获取这个cell所在的地址
void *leaf_node_cell(void *node, uint32_t cell_num) {
    return node + LEAF_NODE_HEADER_SIZE + cell_num * LEAF_NODE_CELL_SIZE;
}

// 在叶子节点中，根据node节点的地址和cell的num来获取这个cell的key所在的地址
uint32_t *leaf_node_key(void *node, uint32_t cell_num) { return leaf_node_cell(node, cell_num); }

// 在叶子节点中，根据node节点的地址和cell的num来获取这个cell的value所在的地址
void *leaf_node_value(void *node, uint32_t cell_num) { return leaf_node_cell(node, cell_num) + LEAF_NODE_KEY_SIZE; }

// 在叶子节点中，初始化node，将该node中的num_cells的值置为0
void initialize_leaf_node(void *node) {
    set_node_type(node, NODE_LEAF);
    set_node_root(node, false);
    *leaf_node_num_cells(node) = 0;
    *leaf_node_next_leaf(node) = 0; // 0 represents no sibling
}

// 序列化行数据
// 将Row结构体中的数据复制到目标地址
void serialize_row(Row *source, void *destination) {
    memcpy(destination + ID_OFFSET, &(source->id), ID_SIZE);
    memcpy(destination + USERNAME_OFFSET, source->name, USERNAME_SIZE);
    memcpy(destination + EMAIL_OFFSET, source->email, EMAIL_SIZE);
}

// 反序列化行数据
// 从源地址复制数据到目标Row结构体中
void deserialize_row(void *source, Row *destination) {
    memcpy(&(destination->id), source + ID_OFFSET, ID_SIZE);
    memcpy(destination->name, source + USERNAME_OFFSET, USERNAME_SIZE);
    memcpy(destination->email, source + EMAIL_OFFSET, EMAIL_SIZE);
}

// 使用Pager来管理页
typedef struct {
    // 文件句柄
    int file_descriptor;
    // 文件中字符的长度
    uint32_t file_length;
    // page number，表示一个table有多少个page
    uint32_t num_pages;
    // 指向页的指针数组
    // 每个页的大小为PAGE_SIZE，最多TABLE_MAX_PAGES个页
    void *pages[TABLE_MAX_PAGES];
} Pager;

// 定义表结构体用于存储表的元数据
typedef struct {
    uint32_t root_page_num; // 根page的编号
    Pager *pager;
} Table;

/*
lseek 和 read 是两个独立的系统调用，它们通过文件描述符的内部文件指针进行协作。
lseek 的作用是设置文件指针的位置。一旦 lseek成功执行，文件指针就已经被移动到了正确的位置。
后续的 read 函数不再需要 offset变量，因为它会从当前文件指针的位置开始写入数据。
read的作用是从文件指针的当前位置开始读PAGE_SIZE大小的数据
*/
// 从pager中获取page页面的地址
void *get_pages(Pager *pager, uint32_t page_num) {

    if (page_num > TABLE_MAX_PAGES) {
        printf("Tried to fetch page number out of bounds. %d > %d\n", page_num, TABLE_MAX_PAGES);
        exit(EXIT_FAILURE);
    }

    // 如果page_num那一页不在内存中
    if (pager->pages[page_num] == NULL) {
        // 创建内存页
        void *page = malloc(PAGE_SIZE);

        // 总的页面数， 如果file_length不是正好是PAGE_SIZE的整数倍，那么就应该+1
        uint32_t num_pages = pager->file_length / PAGE_SIZE;

        // We might save a partial page at the end of the file
        if (pager->file_length % PAGE_SIZE) {
            num_pages += 1;
        }

        if (page_num <= num_pages) {
            // 从db文件中读取该页存到page页中
            lseek(pager->file_descriptor, page_num * PAGE_SIZE, SEEK_SET);
            ssize_t bytes_read = read(pager->file_descriptor, page, PAGE_SIZE);

            if (bytes_read == -1) {
                printf("Error reading file: %d\n", errno);
                exit(EXIT_FAILURE);
            }
        }

        pager->pages[page_num] = page;

        if (page_num >= pager->num_pages) {
            pager->num_pages = page_num + 1;
        }
    }

    return pager->pages[page_num];
}

// 定义cursor游标，用于代表指向表的某个一个位置
/*
游标表示表中的一个位置。当我们的表是一个简单的行数组时（array of rows），我们使用给出的行号就可以访问行数据。
现在，表变成了一棵 btree，我们通过节点的 page number 和节点内的单元格号（cell number）来识别一个位置。
*/

typedef struct {
    Table *table;
    uint32_t page_num; // 游标指向位置所在的page编号
    uint32_t cell_num; // 游标指向位置所在的cell编号
    bool end_of_table; // 是否是指向表的最后
} Cursor;

// 推进游标
void cursor_advance(Cursor *cursor) {

    uint32_t page_num = cursor->page_num;
    void *node = get_pages(cursor->table->pager, page_num);

    cursor->cell_num += 1;
    // 每当我们想将游标推进到叶子节点的末尾时，就可以检查叶子节点是否有兄弟节点。
    // 如果有，跳到兄弟节点。否则，我们就结束在表的末尾。
    if (cursor->cell_num >= (*leaf_node_num_cells(node))) {
        /* Advance to next leaf node */
        uint32_t next_page_num = *leaf_node_next_leaf(node);
        if (next_page_num == 0) {
            /* This was rightmost leaf */
            cursor->end_of_table = true;
        } else {
            cursor->page_num = next_page_num;
            cursor->cell_num = 0;
        }
    }
}

uint32_t get_node_max_key(Pager *pager, void *node) {
    if (get_node_type(node) == NODE_LEAF) {
        return *leaf_node_key(node, *leaf_node_num_cells(node) - 1);
    }
    void *right_child = get_pages(pager, *internal_node_right_child(node));
    return get_node_max_key(pager, right_child);
}

// 左右叶子节点中被分配的cell个数
const uint32_t LEAF_NODE_RIGHT_SPLIT_COUNT = (LEAF_NODE_MAX_CELLS + 1) / 2;
const uint32_t LEAF_NODE_LEFT_SPLIT_COUNT = (LEAF_NODE_MAX_CELLS + 1) - LEAF_NODE_RIGHT_SPLIT_COUNT;

uint32_t internal_node_find_child(void *node, uint32_t key) {
    /*
    Return the index of the child which should contain
    the given key.
    */

    uint32_t num_keys = *internal_node_num_keys(node);

    /* Binary search */
    uint32_t min_index = 0;
    uint32_t max_index = num_keys; /* there is one more child than key */

    while (min_index != max_index) {
        uint32_t index = (min_index + max_index) / 2;
        uint32_t key_to_right = *internal_node_key(node, index);
        if (key_to_right >= key) {
            max_index = index;
        } else {
            min_index = index + 1;
        }
    }

    return min_index;
}

// 在叶子节点中以二分法寻找相应的key
Cursor *leaf_node_find(Table *table, uint32_t page_num, uint32_t key) {
    // 先获取该page的地址
    void *node = get_pages(table->pager, page_num);

    uint32_t num_cells = *leaf_node_num_cells(node); // 获取该node有多少个cell
    Cursor *cursor = (Cursor *)malloc(sizeof(Cursor));
    cursor->table = table;
    cursor->page_num = page_num;

    // Binary search
    uint32_t min_index = 0;
    uint32_t one_past_max_index = num_cells;

    while (min_index != one_past_max_index) {
        uint32_t index = (min_index + one_past_max_index) / 2;
        uint32_t key_at_index = *leaf_node_key(node, index);

        if (key_at_index == key) // 找到了key
        {
            cursor->cell_num = index;
            return cursor;
        } else if (key < key_at_index) { // key比当前位置的key_at_index更小
            one_past_max_index = index;
        } else { // key比当前位置的key_at_index更大
            min_index = index + 1;
        }
    }
    cursor->cell_num = min_index;
    return cursor;
}

// 在内部节点中递归搜索B-Tree寻找相应的key
Cursor *internal_node_find(Table *table, uint32_t page_num, uint32_t key) {
    void *node = get_pages(table->pager, page_num);

    uint32_t child_index = internal_node_find_child(node, key);
    uint32_t child_num = *internal_node_child(node, child_index);
    void *child = get_pages(table->pager, child_num);
    switch (get_node_type(child)) {
    case NODE_LEAF:
        return leaf_node_find(table, child_num, key);
    case NODE_INTERNAL:
        return internal_node_find(table, child_num, key);
    }
}

/*
Until we start recycling free pages, new pages will always go onto the end of the database file
*/
// 获得未使用的page num，现阶段没有回收page，所以新page将会是最大的值
uint32_t get_unused_page_num(Pager *pager) { return pager->num_pages; }

uint32_t *node_parent(void *node) { return node + PARENT_POINTER_OFFSET; }

// 创建新根节点
void create_new_root(Table *table, uint32_t right_child_page_num) {
    /*
    Handle splitting the root. Old root copied to new page, becomes left child.
    Address of right child passed in.
    Re-initialize root page to contain the new root node.
    New root node points to two children.
    */

    void *root = get_pages(table->pager, table->root_page_num);
    void *right_child = get_pages(table->pager, right_child_page_num);
    uint32_t left_child_page_num = get_unused_page_num(table->pager);
    void *left_child = get_pages(table->pager, left_child_page_num);

    if (get_node_type(root) == NODE_INTERNAL) {
        initialize_internal_node(right_child);
        initialize_internal_node(left_child);
    }

    /* Left child has data copied from old root */
    memcpy(left_child, root, PAGE_SIZE);
    set_node_root(left_child, false);

    if (get_node_type(left_child) == NODE_INTERNAL) {
        void *child;
        for (int i = 0; i < *internal_node_num_keys(left_child); i++) {
            child = get_pages(table->pager, *internal_node_child(left_child, i));
            *node_parent(child) = left_child_page_num;
        }
        child = get_pages(table->pager, *internal_node_right_child(left_child));
        *node_parent(child) = left_child_page_num;
    }

    /* Root node is a new internal node with one key and two children */
    initialize_internal_node(root);
    set_node_root(root, true);
    *internal_node_num_keys(root) = 1;
    *internal_node_child(root, 0) = left_child_page_num;
    uint32_t left_child_max_key = get_node_max_key(table->pager, left_child);
    *internal_node_key(root, 0) = left_child_max_key;
    *internal_node_right_child(root) = right_child_page_num;

    *node_parent(left_child) = table->root_page_num;
    *node_parent(right_child) = table->root_page_num;
}

void update_internal_node_key(void *node, uint32_t old_key, uint32_t new_key) {
    uint32_t old_child_index = internal_node_find_child(node, old_key);
    *internal_node_key(node, old_child_index) = new_key;
}

void internal_node_split_and_insert(Table *table, uint32_t parent_page_num, uint32_t child_page_num);

void internal_node_insert(Table *table, uint32_t parent_page_num, uint32_t child_page_num) {
    /*
    Add a new child/key pair to parent that corresponds to child
    */

    void *parent = get_pages(table->pager, parent_page_num);
    void *child = get_pages(table->pager, child_page_num);
    uint32_t child_max_key = get_node_max_key(table->pager, child);
    uint32_t index = internal_node_find_child(parent, child_max_key);

    uint32_t original_num_keys = *internal_node_num_keys(parent);

    if (original_num_keys >= INTERNAL_NODE_MAX_KEYS) {
        internal_node_split_and_insert(table, parent_page_num, child_page_num);
        return;
    }
    uint32_t right_child_page_num = *internal_node_right_child(parent);

    /*
        An internal node with a right child of INVALID_PAGE_NUM is empty
   */
    if (right_child_page_num == INVALID_PAGE_NUM) {
        *internal_node_right_child(parent) = child_page_num;
        return;
    }

    void *right_child = get_pages(table->pager, right_child_page_num);

    /*
        If we are already at the max number of cells for a node, we cannot increment
        before splitting. Incrementing without inserting a new key/child pair
        and immediately calling internal_node_split_and_insert has the effect
        of creating a new key at (max_cells + 1) with an uninitialized value
*/
    *internal_node_num_keys(parent) = original_num_keys + 1;

    if (child_max_key > get_node_max_key(table->pager, right_child)) {
        /* Replace right child */
        *internal_node_child(parent, original_num_keys) = right_child_page_num;
        *internal_node_key(parent, original_num_keys) = get_node_max_key(table->pager, right_child);
        *internal_node_right_child(parent) = child_page_num;
    } else {
        /* Make room for the new cell */
        for (uint32_t i = original_num_keys; i > index; i--) {
            void *destination = internal_node_cell(parent, i);
            void *source = internal_node_cell(parent, i - 1);
            memcpy(destination, source, INTERNAL_NODE_CELL_SIZE);
        }
        *internal_node_child(parent, index) = child_page_num;
        *internal_node_key(parent, index) = child_max_key;
    }
}

// 处理旧节点，生成新节点
void leaf_node_split_and_insert(Cursor *cursor, uint32_t key, Row *value) {
    /*
    Create a new node and move half the cells over.
    Insert the new value in one of the two nodes.
    Update parent or create a new parent.
    */

    void *old_node = get_pages(cursor->table->pager, cursor->page_num);
    uint32_t old_max = get_node_max_key(cursor->table->pager, old_node);
    uint32_t new_page_num = get_unused_page_num(cursor->table->pager);
    void *new_node = get_pages(cursor->table->pager, new_page_num);
    initialize_leaf_node(new_node);
    *node_parent(new_node) = *node_parent(old_node);

    *leaf_node_next_leaf(new_node) = *leaf_node_next_leaf(old_node);
    *leaf_node_next_leaf(old_node) = new_page_num;
    /*
   All existing keys plus new key should be divided
   evenly between old (left) and new (right) nodes.
   Starting from the right, move each key to correct position.
   */
    for (int32_t i = LEAF_NODE_MAX_CELLS; i >= 0; i--) {
        void *destination_node;
        if (i >= LEAF_NODE_LEFT_SPLIT_COUNT) {
            destination_node = new_node;
        } else {
            destination_node = old_node;
        }
        uint32_t index_within_node = i % LEAF_NODE_LEFT_SPLIT_COUNT;
        void *destination = leaf_node_cell(destination_node, index_within_node);

        if (i == cursor->cell_num) {
            serialize_row(value, leaf_node_value(destination_node, index_within_node));
            *leaf_node_key(destination_node, index_within_node) = key;
        } else if (i > cursor->cell_num) {
            memcpy(destination, leaf_node_cell(old_node, i - 1), LEAF_NODE_CELL_SIZE);
        } else {
            memcpy(destination, leaf_node_cell(old_node, i), LEAF_NODE_CELL_SIZE);
        }
    }

    /* Update cell count on both leaf nodes */
    *(leaf_node_num_cells(old_node)) = LEAF_NODE_LEFT_SPLIT_COUNT;
    *(leaf_node_num_cells(new_node)) = LEAF_NODE_RIGHT_SPLIT_COUNT;

    // 需要更新节点的父节点
    if (is_node_root(old_node)) {
        return create_new_root(cursor->table, new_page_num);
    } else {
        uint32_t parent_page_num = *node_parent(old_node);
        uint32_t new_max = get_node_max_key(cursor->table->pager, old_node);
        void *parent = get_pages(cursor->table->pager, parent_page_num);

        update_internal_node_key(parent, old_max, new_max);
        internal_node_insert(cursor->table, parent_page_num, new_page_num);
        return;
    }
}

// 定义一个函数用来插入一个键值对儿到一个叶子节点中
// 它将采用游标来作为需要插入键值对儿的位置的表示
void leaf_node_insert(Cursor *cursor, uint32_t key, Row *value) {

    // 获取要插入的节点
    void *node = get_pages(cursor->table->pager, cursor->page_num);

    uint32_t num_cells = *leaf_node_num_cells(node);
    if (num_cells >= LEAF_NODE_MAX_CELLS) { // 判断该节点还能否继续插入
        // Node full
        leaf_node_split_and_insert(cursor, key, value);
        return;
    }

    if (cursor->cell_num < num_cells) { // 如果插入的位置在该节点的中间，将插入位置后面的节点向后挪一个cell的位置
        // Make room for new cell
        for (uint32_t i = num_cells; i > cursor->cell_num; i--) {
            memcpy(leaf_node_cell(node, i), leaf_node_cell(node, i - 1), LEAF_NODE_CELL_SIZE);
        }
    }

    *(leaf_node_num_cells(node)) += 1;                             // cell数量+1
    *(leaf_node_key(node, cursor->cell_num)) = key;                // 给插入的cell的key赋值
    serialize_row(value, leaf_node_value(node, cursor->cell_num)); // 给插入的cell的value赋值
}

// ******************重点函数******************
// 该函数根据行号计算出该行的数据在内存中的地址
// 在插入一行时，先根据当前内存中已经存储的行数，计算出内存中下一行存储的起始地址，这样新的一行就直接存储在该地址上
// 如果该行所在的页还没有被分配内存，则分配新的页

// 在查询时，通过行号计算出该行在内存中的地址，然后读取该地址上的数据
// void *row_slot(Table *table, uint32_t row_num) { // row_num是行号, 也就是table中存储的总数据行数
void *cursor_value(Cursor *cursor) { // 算出游标现在指向位置的地址

    // 直接从游标中获取page_num
    uint32_t page_num = cursor->page_num;

    // 获取page的地址
    void *page = get_pages(cursor->table->pager, page_num);

    return leaf_node_value(page, cursor->cell_num);
}

// 打印提示符
void print_prompt() { printf("cheng db > "); }

// 读取用户输入
// 使用getline函数读取一行输入，并将其存储在InputBuffer中
void read_input(InputBuffer *input_buffer) {
    // geline的使用
    // getline(char **lineptr, size_t *n, FILE *stream) 返回输入的字节数
    // 如果lineptr为NULL，则会自动分配内存
    ssize_t bytes_read = getline(&(input_buffer->buffer), &(input_buffer->buffer_length), stdin);

    if (bytes_read <= 0) {
        printf("Error reading input\n");
        exit(EXIT_FAILURE);
    }

    // 忽略最后的换行符
    input_buffer->input_length = bytes_read - 1;
    input_buffer->buffer[bytes_read - 1] = 0;
}

// 释放InputBuffer的内存
void close_input_buffer(InputBuffer *input_buffer) {
    free(input_buffer->buffer);
    free(input_buffer);
}

// 释放Pager的内存
void close_pager(Pager *pager) {
    for (int i = 0; i < TABLE_MAX_PAGES; i++) {
        if (pager->pages[i] != NULL) {
            free(pager->pages[i]); // 释放每个页的内存，因为在row_slot中会根据需要分配内存，所以在这里需要释放
            pager->pages[i] = NULL;
        }
    }
    free(pager);
    pager = NULL;
}

// 释放表的内存
void close_table(Table *table) {
    close_pager(table->pager);
    free(table);  // 释放表的内存
    table = NULL; // 将指针置为NULL，避免悬空指针
}
/*
lseek 和 write 是两个独立的系统调用，它们通过文件描述符的内部文件指针进行协作。
lseek 的作用是设置文件指针的位置。一旦 lseek成功执行，文件指针就已经被移动到了正确的位置。
后续的 write 函数不再需要 offset变量，因为它会从当前文件指针的位置开始写入数据。
write的作用是从文件指针的当前位置开始写入数据。
*/
// page_num page的num，也就是第几个page
// size，这一页中需要写入文件的大小
void pager_flush(Pager *pager, uint32_t page_num) {
    if (pager->pages[page_num] == NULL) {
        printf("Tried to flush null page\n");
        exit(EXIT_FAILURE);
    }

    // 先通过lseek将文件指针的位置移到需要写入文件的位置
    off_t offset = lseek(pager->file_descriptor, page_num * PAGE_SIZE, SEEK_SET);

    if (offset == -1) {
        printf("Error seeking: %d\n", errno);
        exit(EXIT_FAILURE);
    }

    // 将从pager->pages[page_num]位置开始 到 pager->pages[page_num] + PAGE_SIZE
    // 这个地址之间的数据写入文件
    ssize_t bytes_written = write(pager->file_descriptor, pager->pages[page_num], PAGE_SIZE);

    if (bytes_written == -1) {
        printf("Error writing: %d\n", errno);
        exit(EXIT_FAILURE);
    }
}

// flush页缓存到磁盘
// 关闭数据文件
// 释放Pager、table数据结构的内存
void close_db(Table *table) {
    Pager *pager = table->pager;

    // 将每一页都flush到文件中
    for (size_t i = 0; i < pager->num_pages; i++) {
        pager_flush(pager, i);
        free(pager->pages[i]);
        pager->pages[i] = NULL;
    }

    // 保证一行数据的内容在一个page中

    // 关闭文件
    int result = close(pager->file_descriptor);
    if (result == -1) {
        printf("Error closing db file.\n");
        exit(EXIT_FAILURE);
    }

    // 释放Pager、table数据结构的内存
    close_table(table);
}

// 创建一个新的InputBuffer
// 该函数在堆上分配内存，并初始化InputBuffer的字段
InputBuffer *new_input_buffer() {
    // 堆上申请InputBuffer内存
    InputBuffer *input_buffer = (InputBuffer *)malloc(sizeof(InputBuffer));

    // 初始化InputBuffer
    if (input_buffer == NULL) {
        printf("Memory allocation failed\n");
        exit(EXIT_FAILURE);
    }

    input_buffer->buffer = NULL;
    input_buffer->buffer_length = 0;
    input_buffer->input_length = 0;
    return input_buffer;
}

// 打印常量数据
void print_constants() {
    printf("ROW_SIZE: %d\n", ROW_SIZE);
    printf("COMMON_NODE_HEADER_SIZE: %d\n", COMMON_NODE_HEADER_SIZE);
    printf("LEAF_NODE_HEADER_SIZE: %d\n", LEAF_NODE_HEADER_SIZE);
    printf("LEAF_NODE_CELL_SIZE: %d\n", LEAF_NODE_CELL_SIZE);
    printf("LEAF_NODE_SPACE_FOR_CELLS: %d\n", LEAF_NODE_SPACE_FOR_CELLS);
    printf("LEAF_NODE_MAX_CELLS: %d\n", LEAF_NODE_MAX_CELLS);
}

void indent(uint32_t level) {
    for (uint32_t i = 0; i < level; i++) {
        printf("  ");
    }
}

// 打印叶子节点信息
void print_tree(Pager *pager, uint32_t page_num, uint32_t indentation_level) {
    void *node = get_pages(pager, page_num);
    uint32_t num_keys, child;

    switch (get_node_type(node)) {
    case (NODE_LEAF):
        num_keys = *leaf_node_num_cells(node);
        indent(indentation_level);
        printf("- leaf (size %d)\n", num_keys);
        for (uint32_t i = 0; i < num_keys; i++) {
            indent(indentation_level + 1);
            printf("- %d\n", *leaf_node_key(node, i));
        }
        break;
    case (NODE_INTERNAL):
        num_keys = *internal_node_num_keys(node);
        indent(indentation_level);
        printf("- internal (size %d)\n", num_keys);

        if (num_keys > 0) {
            for (uint32_t i = 0; i < num_keys; i++) {
                child = *internal_node_child(node, i);
                print_tree(pager, child, indentation_level + 1);

                indent(indentation_level + 1);
                printf("- key %d\n", *internal_node_key(node, i));
            }
            child = *internal_node_right_child(node);

            print_tree(pager, child, indentation_level + 1);
        }

        break;
    }
}

// 处理元命令
MetaCommandResult do_meta_command(InputBuffer *input_buffer, Table *table) {
    if (strcmp(input_buffer->buffer, ".exit") == 0) {
        close_db(table);
        close_input_buffer(input_buffer); // 释放InputBuffer内存
        exit(EXIT_SUCCESS);
    } else if (strcmp(input_buffer->buffer, ".constants") == 0) {
        printf("Constants:\n");
        print_constants();
        return META_COMMAND_SUCCESS;
    } else if (strcmp(input_buffer->buffer, ".btree") == 0) {
        printf("Tree:\n");
        print_tree(table->pager, 0, 0);
        return META_COMMAND_SUCCESS;
    } else if (strcmp(input_buffer->buffer, ".help") == 0) {
        printf("Available commands:\n");
        printf(".exit - Exit the program\n");
        printf(".help - Show this help message\n");
        return META_COMMAND_SUCCESS;
    } else if (strcmp(input_buffer->buffer, ".version") == 0) {
        printf("SQLite version 3.37.2\n"); // 示例版本号
        return META_COMMAND_SUCCESS;
    } else {
        return META_COMMAND_UNRECOGNIZED_COMMAND;
    }
}

// 准备好sql语句
PrepareResult prepare_statement(InputBuffer *input_buffer, Statement *statement) {
    // 把输入参数 str1 和 str2 进行比较，最多比较入参的前 n 个字节
    if (strncmp(input_buffer->buffer, "insert", 6) == 0) {
        statement->type = STATEMENT_INSERT;

        // 解析insert语句，将对应的内容存储到statement的row_to_insert中
        const char s[] = " "; // 分隔符是空格
        char *keyword_string = strtok(input_buffer->buffer, s);
        char *id_string = strtok(NULL, s);
        char *name_string = strtok(NULL, s);
        char *email_string = strtok(NULL, s);

        if (id_string == NULL || name_string == NULL || email_string == NULL) {
            return PREPARE_SYNTAX_ERROR;
        }

        if (strlen(name_string) > COLUMN_NAME_SIZE || strlen(email_string) > COLUMN_EMAIL_SIZE) {
            return PREPARE_STRING_TOO_LONG;
        }

        int id = atoi(id_string);
        if (id < 0) {
            return PREPARE_NAGATIVE_ID;
        }

        statement->row_to_insert.id = id;
        strcpy(statement->row_to_insert.name, name_string);
        strcpy(statement->row_to_insert.email, email_string);

        printf("Prepared insert statement: id=%d, name=%s, email=%s\n", statement->row_to_insert.id,
               statement->row_to_insert.name, statement->row_to_insert.email);

    } else if (strncmp(input_buffer->buffer, "select", 6) == 0) {
        statement->type = STATEMENT_SELECT;
    } else { // 如果输入不是insert或select，则返回PREPARE_UNRECOGNIZED_STATEMENT
        return PREPARE_UNRECOGNIZED_STATEMENT;
    }
    return PREPARE_SUCCESS; // 默认返回成功;
}

// 在table中找到key的位置
// 如果key存在，返回其位置
// 如果key不存在，那么返回这个key应该插入的位置
Cursor *table_find(Table *table, uint32_t key) {
    uint32_t root_page_num = table->root_page_num;            // 从根节点开始寻找
    void *root_node = get_pages(table->pager, root_page_num); // 获取根节点的地址，现在先这么做，后面再去中间节点获取

    if (get_node_type(root_node) == NODE_LEAF) {
        return leaf_node_find(table, root_page_num, key);
    } else {
        return internal_node_find(table, root_page_num, key);
    }
}

// 创建指向表头的游标
// 搜索 key 0 (可能存在的最小的 key)。即使在表中 key
// 0不存在，这个方法也会返回最小id的位置（最左叶子节点的开始位置）。
Cursor *get_start_cursor(Table *table) {
    Cursor *cursor = table_find(table, 0);

    void *node = get_pages(table->pager, cursor->page_num);
    uint32_t num_cells = *leaf_node_num_cells(node);
    cursor->end_of_table = (num_cells == 0);

    return cursor;
}

void internal_node_split_and_insert(Table *table, uint32_t parent_page_num, uint32_t child_page_num) {
    uint32_t old_page_num = parent_page_num;
    void *old_node = get_pages(table->pager, parent_page_num);
    uint32_t old_max = get_node_max_key(table->pager, old_node);

    void *child = get_pages(table->pager, child_page_num);
    uint32_t child_max = get_node_max_key(table->pager, child);

    uint32_t new_page_num = get_unused_page_num(table->pager);

    /*
    Declaring a flag before updating pointers which
    records whether this operation involves splitting the root -
    if it does, we will insert our newly created node during
    the step where the table's new root is created. If it does
    not, we have to insert the newly created node into its parent
    after the old node's keys have been transferred over. We are not
    able to do this if the newly created node's parent is not a newly
    initialized root node, because in that case its parent may have existing
    keys aside from our old node which we are splitting. If that is true, we
    need to find a place for our newly created node in its parent, and we
    cannot insert it at the correct index if it does not yet have any keys
    */
    uint32_t splitting_root = is_node_root(old_node);

    void *parent;
    void *new_node;
    if (splitting_root) {
        create_new_root(table, new_page_num);
        parent = get_pages(table->pager, table->root_page_num);
        /*
        If we are splitting the root, we need to update old_node to point
        to the new root's left child, new_page_num will already point to
        the new root's right child
        */
        old_page_num = *internal_node_child(parent, 0);
        old_node = get_pages(table->pager, old_page_num);
    } else {
        parent = get_pages(table->pager, *node_parent(old_node));
        new_node = get_pages(table->pager, new_page_num);
        initialize_internal_node(new_node);
    }

    uint32_t *old_num_keys = internal_node_num_keys(old_node);

    uint32_t cur_page_num = *internal_node_right_child(old_node);
    void *cur = get_pages(table->pager, cur_page_num);

    /*
    First put right child into new node and set right child of old node to invalid page number
    */
    internal_node_insert(table, new_page_num, cur_page_num);
    *node_parent(cur) = new_page_num;
    *internal_node_right_child(old_node) = INVALID_PAGE_NUM;
    /*
    For each key until you get to the middle key, move the key and the child to the new node
    */
    for (int i = INTERNAL_NODE_MAX_KEYS - 1; i > INTERNAL_NODE_MAX_KEYS / 2; i--) {
        cur_page_num = *internal_node_child(old_node, i);
        cur = get_pages(table->pager, cur_page_num);

        internal_node_insert(table, new_page_num, cur_page_num);
        *node_parent(cur) = new_page_num;

        (*old_num_keys)--;
    }

    /*
    Set child before middle key, which is now the highest key, to be node's right child,
    and decrement number of keys
    */
    *internal_node_right_child(old_node) = *internal_node_child(old_node, *old_num_keys - 1);
    (*old_num_keys)--;

    /*
    Determine which of the two nodes after the split should contain the child to be inserted,
    and insert the child
    */
    uint32_t max_after_split = get_node_max_key(table->pager, old_node);

    uint32_t destination_page_num = child_max < max_after_split ? old_page_num : new_page_num;

    internal_node_insert(table, destination_page_num, child_page_num);
    *node_parent(child) = destination_page_num;

    update_internal_node_key(parent, old_max, get_node_max_key(table->pager, old_node));

    if (!splitting_root) {
        internal_node_insert(table, *node_parent(old_node), new_page_num);
        *node_parent(new_node) = *node_parent(old_node);
    }
}

// 执行插入操作
ExecuteResult execute_insert(Statement *statement, Table *table) {

    void *node = get_pages(table->pager, table->root_page_num);
    uint32_t num_cells = *leaf_node_num_cells(node);

    Row *row_to_insert = &(statement->row_to_insert);

    // 插入时直接向最后面插入，所以获取最尾端的游标
    // Cursor *end_cursor = get_end_cursor(table);
    // 不再插入最尾端，而是在找到node之后，将行插入相应的位置

    int key_to_insert = row_to_insert->id;
    Cursor *cursor = table_find(table, key_to_insert);

    // 将当前的内容插入到该行中
    // 获取该内容statement中insert的内容应该存储在哪个内存地址
    // void *row_addr = cursor_value(end_cursor);
    // serialize_row函数将Row结构体中的数据复制到指定的内存地址
    // serialize_row(&(statement->row_to_insert), row_addr);
    // table->num_rows += 1; // 更新表的行数

    if (cursor->cell_num < num_cells) { // 判断是否key重复。如果cell_num的值大于等于num_cells，说明应该将key插入到最后
        uint32_t key_at_index = *leaf_node_key(node, cursor->cell_num);
        if (key_at_index == key_to_insert) {
            return EXECUTE_DUPLICATE_KEY;
        }
    }
    leaf_node_insert(cursor, key_to_insert, row_to_insert); // 向叶子节点插入内容

    free(cursor);
    cursor = NULL;

    return EXECUTE_SUCCESS; // 返回执行成功
}

// 打印行数据
void print_row(Row *row) { printf("(id=%d, name=%s, email=%s)\n", row->id, row->name, row->email); }

// 打印行数据
ExecuteResult execute_select(Statement *statement, Table *table) {

    // 从最开始的游标开始遍历
    Cursor *cursor = get_start_cursor(table);

    // 打印 table->num_rows 中每一行的数据
    while (cursor->end_of_table != true) {
        // 获取每一行的内存地址
        void *row_addr = cursor_value(cursor);
        Row deserialized_row;
        // 反序列化行数据，将内存中的数据转换为Row结构体
        deserialize_row(row_addr, &deserialized_row);
        print_row(&deserialized_row); // 打印行数据
        cursor_advance(cursor);       // 游标向前进一行
    }

    free(cursor);

    return EXECUTE_SUCCESS; // 返回执行成功
}

// 执行sql语句
ExecuteResult execute_statement(Statement *statement, Table *table) {
    switch (statement->type) {
    case STATEMENT_INSERT:
        printf("Executing insert statement\n");
        // 这里可以添加插入逻辑
        // 例如，将statement->row_to_insert插入到表中
        printf("Inserted row: id=%d, name=%s, email=%s\n", statement->row_to_insert.id, statement->row_to_insert.name,
               statement->row_to_insert.email);

        return execute_insert(statement, table); // 这里传入NULL是因为没有实际的表结构

    case STATEMENT_SELECT:
        printf("Executing select statement\n");
        return execute_select(statement, table); // 执行select语句

    default:
        printf("Unknown statement type\n");
        return EXECUTE_FAILURE; // 如果语句类型未知，返回执行失败
    }
}

// 打开一个文件，并初始化Pager
Pager *pager_open(const char *filename) {

    int fd = open(filename,
                  O_RDWR |     // Read/Write mode
                      O_CREAT, // Create file if it does not exist
                  S_IWUSR |    // User write permission
                      S_IRUSR  // User read permission);
    );

    if (fd == -1) {
        printf("Unable to open file\n");
        exit(EXIT_FAILURE);
    }

    Pager *pager = (Pager *)malloc(sizeof(Pager));

    pager->file_descriptor = fd;
    pager->file_length = lseek(fd, 0, SEEK_END);

    pager->num_pages = (pager->file_length / PAGE_SIZE); // 第一次打开就会是0

    // 保证一行数据的内容不会分散存储在两个page中
    if (pager->file_length % PAGE_SIZE != 0) {
        printf("Db file is not a whole number of pages. Corrupt file.\n");
        exit(EXIT_FAILURE);
    }

    for (int i = 0; i < TABLE_MAX_PAGES; i++) {
        pager->pages[i] = NULL; // 初始化页指针为NULL
    }

    return pager;
}

// 初始化table
Table *db_open(const char *filename) {
    Pager *pager = pager_open(filename);

    Table *table = (Table *)malloc(sizeof(Table));
    if (table == NULL) {
        printf("Memory allocation failed for table\n");
        exit(EXIT_FAILURE);
    }

    table->root_page_num = 0;
    table->pager = pager;

    // 如果是新的New database file，Initialize page 0 as leaf node.
    if (pager->num_pages == 0) {
        void *root_node = get_pages(pager, 0);
        initialize_leaf_node(root_node);
        set_node_root(root_node, true);
    }

    return table; // 返回新创建的表
}

int main(int argc, char *argv[]) {

    if (argc < 2) {
        printf("Must supply a database filename.\n");
        exit(EXIT_FAILURE);
    }
    char *filename = argv[1];

    Table *table = db_open(filename); // 创建一个新的表
    InputBuffer *input_buffer = new_input_buffer();
    while (true) {
        print_prompt();

        // 读取用户输入行
        read_input(input_buffer);

        // 如果输入以点开头，则认为是元命令
        if (input_buffer->buffer[0] == '.') {
            switch (do_meta_command(input_buffer, table)) {
            case META_COMMAND_SUCCESS:
                continue; // 成功执行元命令后，继续外层while循环，该continue作用于外层while循环

            case META_COMMAND_UNRECOGNIZED_COMMAND:
                printf("Unrecognized command '%s'.\n", input_buffer->buffer);
                continue; // 继续外层while循环;

            default:
                printf("Unknown error\n");
                continue; // 继续外层while循环;
            }
        }

        Statement statement;
        PrepareResult prepareResult = prepare_statement(input_buffer, &statement);
        switch (prepareResult) {
        case PREPARE_SUCCESS:
            break;

        case PREPARE_UNRECOGNIZED_STATEMENT:
            printf("Unrecognized statement '%s'.\n", input_buffer->buffer);
            continue; // 继续外层while循环;

        case PREPARE_SYNTAX_ERROR:
            printf("Syntax error. Usage: insert <id> <name> <email>\n");
            continue; // 继续外层while循环;
        case PREPARE_NAGATIVE_ID:
            printf("ID must be positive\n");
            continue;
        case PREPARE_STRING_TOO_LONG:
            printf("name or email string is too long. name max length is 32, email max length is 255.\n ");
            continue;
        default:
            break;
        }

        ExecuteResult executeResult = execute_statement(&statement, table); // 执行准备好的语句
        switch (executeResult) {
        case EXECUTE_SUCCESS:
            break;
        case EXECUTE_TABLE_FULL:
            printf("Error: Table full. Cannot insert new row.\n");
            break;

        case (EXECUTE_DUPLICATE_KEY):
            printf("Error: Duplicate key.\n");
            break;

        case EXECUTE_FAILURE:
            printf("Error: execute fail.\n");
            break;

        default:
            break;
        }
    }
}